package 剑指offer;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * @author zhangmin
 * @create 2021-11-21 13:18
 *
 * 动态规划
 */
public class day10_46_48 {

    /**===========================================================================================================================
     * 剑指 Offer 46. 把数字翻译成字符串
     * 给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。
     * 一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字<有多少种不同的翻译方法>。
     * dp:dp[i]表示前i个数字的最多翻译方法
     * dp[i]=dp[i-1](第i个数字单独翻译)+dp[i-2](第i个数字和i-1共同翻译)
     * */
    public int translateNum1(int num) {
        char[] nums = Integer.toString(num).toCharArray();
        System.out.println(nums.length);
        int n=nums.length;
        int[] dp=new int[n];
        dp[0]=1;
        for (int i = 1; i < n; i++) {
            int pre=(nums[i-1]-'0')*10+(nums[i]-'0');
            if (pre>25||pre<10){
                //需要两个连起来在10到25之间才能和前一共同翻译
                dp[i]=dp[i-1];
            }else {
                if (i==1){
                    dp[i]=2;
                }else {
                    dp[i]=dp[i-1]+dp[i-2];
                }
            }
        }
        return dp[n-1];
    }
    //题解：不需要转换成数字进行比较，状态压缩
    public int translateNum(int num) {
        String s = String.valueOf(num);
        int p=0,q=0,r=1;
        for (int i = 0; i < s.length(); i++) {
            p=q;
            q=r;
            r=0;
            r+=q;
            if (i==0){
                continue;
            }
            String pre=s.substring(i-1,i+1);
            if (pre.compareTo("25")<=0&&pre.compareTo("10")>=0){
                r+=p;
            }
        }
        return r;
    }

    /**===========================================================================================================================
     * 剑指 Offer 48. 最长不含重复字符的子字符串
     * 请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
     * 双指针滑动窗口：用set记录windows中的元素
     * */
    public int lengthOfLongestSubstring1(String s) {
        int n=s.length();
        if (n==0) return 0;
        if (n==1) return 1;
        int i=0,j=0;
        Set<Character> set=new HashSet<>();
        set.add(s.charAt(i));
        int res=1;
        while (j<s.length()-1){
            j++;
            while (set.contains(s.charAt(j))&&i<j){
                //元素已经在set中存在了。缩小左边界
                set.remove(s.charAt(i));
                i++;
            }
            //将右边界加入set
            set.add(s.charAt(j));
            res=Math.max(res,j-i+1);
        }
        return res;
    }
    //滑动窗口套模板
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character,Integer> window=new HashMap<>();
        int left=0,right=0;
        int res=0;
        while (right<s.length()){
            char c=s.charAt(right);
            right++;
            window.put(c,window.getOrDefault(c,0)+1);
            while (window.get(c)>1){
                char d=s.charAt(left);
                left++;
                window.put(d,window.getOrDefault(d,0)-1);
            }
            res=Math.max(res,right-left);//right已经++过了
        }
        return res;
    }
}
